import collections


class Solution(object):
    def gardenNoAdj(self, n, paths):
        d = collections.defaultdict(set)
        for u, v in paths:
            d[u - 1].add(v - 1)
            d[v - 1].add(u - 1)
        ans = [0] * n
        for i in range(n):
            if not ans[i]:
                ans[i] = 1
                now = set()
                for node in d[i]:
                    now.add(node)
                while now:
                    node = now.pop()
                    p = set()
                    for v in d[node]:
                        if ans[v]:
                            p.add(ans[v])
                        else:
                            if v not in now:
                                now.add(v)
                    for k in range(1, 5):
                        if k not in p:
                            ans[node] = k
                            break
        return ans


data = Solution()
n = 3
paths = [[1, 2], [2, 3], [3, 1]]
print(data.gardenNoAdj(n, paths))
